package com.cty._05_Ability._54_KthNodeInBST;

/**
 * @Auther: cty
 * @Date: 2020/7/21 17:31
 * @Description: 面试题54：二叉搜索树的第k个结点
 * 题目：给定一棵二叉搜索树，请找出其中的第k大的结点。
 * @version: 1.0
 */
public class KthNodeInBST {
    public static int k;

    public static BinaryTreeNode kthNodeInBST(BinaryTreeNode treeRoot, int kNum){
        if(treeRoot == null || kNum<=0)
            return null;

        k = kNum;
        return inOrder(treeRoot);
    }  // end kthNodeInBST()

    private static BinaryTreeNode inOrder(BinaryTreeNode current){
        if(current == null)
            return null;

        BinaryTreeNode target = null;
        target = inOrder(current.leftChild);

        if(target == null){
            if(k == 1)
                target = current;
            k--;
        }
        if(target == null)
            target = inOrder(current.rightChild);

        return target;
    }  // end inOrder()

}  // end class

class BinaryTreeNode {
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}
    public BinaryTreeNode(int value){this.value = value;};
}
